package array

import (
	"fmt"
	"sort"
)

// 执行用时 36 62.05%
// 内存消耗 7.5mb 36.58%
// 双指针

func ThreeSum(nums []int) [][]int {
	res := make([][]int, 0)

	numsLength := len(nums)

	if numsLength < 3 {
		return res
	}

	sort.Ints(nums)
	fmt.Println("after sort:", nums)

	for first := 0; first < numsLength; first++ {
		// nums[first] == nums[first-1] 那么结果是一样的
		if first > 0 && nums[first] == nums[first-1] {
			continue
		}
		third := numsLength - 1
		target := -1 * nums[first]
		// 遍历第一个数为nums[first]的所有可能性
		for second := first + 1; second < numsLength; second++ {
			// nums[second] 取 nums[first+2]以后的数
			// 也就是说可以允许nums[first]==nums[second] (second==first+1) {nums[first],nums[first]}
			// 因为如果nums[second]==nums[second-1]
			// 那么说明{nums[first],nums[second]}这个情况就已经遍历过了
			// 如果定下了{nums[first],nums[second]}，那么第三个数是固定的
			// 题目要求不能重复，那么就只有一种情况
			if second > first+1 && nums[second] == nums[second-1] {
				continue
			}

			// 因为从小到大排序了，如果nums[second]+nums[third]，那么就是nums[third]大了
			for second < third && nums[second]+nums[third] > target {
				third--
			}

			// 第二个没有配对的第三个，那么第二个就没必要++了
			if second == third {
				break
			}
			if nums[second]+nums[third] == target {
				res = append(res, []int{nums[first], nums[second], nums[third]})
			}
		}

	}

	return res

}
